package org.TheSubject;

import java.util.PriorityQueue;

public class TopK {
    static public int getTopK(int[] nums,int k){
        int size=nums.length;
        if (k>size||k<1){
           throw new ArrayIndexOutOfBoundsException();
        }
        //return getTopKByPriorityQueue(nums,k);
        return getTopKByPartition(nums,k);
    }
    static public int getTopKByPriorityQueue(int[] nums, int k){
        PriorityQueue<Integer> first = new PriorityQueue<>(k);
        for (int i=0;i<k;i++){
            first.offer(nums[i]);
        }
        int size=nums.length;
        for(int i=k;i<size;i++){
            int peek=first.peek();
            if (peek<nums[i]){
                first.poll();
                first.offer(nums[i]);
            }
        }
        return first.peek();
    }
    static public int getTopKByPartition(int[] nums,int k){
        int right=nums.length;
        int left=0;
        int partition = partition(nums, left, right);
        int targetIndex=right-k;
        while (partition!=targetIndex){
            if (partition<targetIndex){
                partition=partition(nums,partition+1,right);
            }else {
                partition=partition(nums,left,partition-1);
            }
        }
        return nums[partition];
    }
    static public int partition(int[] nums,int left,int right){
       int temp=nums[left];
       while (left<right){
           while (left<right&&nums[right]>=temp){
               right--;
           }
           nums[left]=nums[right];
           while (left<right&&nums[left]<=temp){
               left++;
           }
           nums[right]=nums[left];
       }
       nums[left]=temp;
       return left;
    }
    public static void main(String[] args) {
        int[] test={1,2,9,6,0,7,10,3};
        int partition = partition(test, 0, 7);
        System.out.println(partition);

        for (int i : test) {
            System.out.print(i+",");
        }
    }
}
